import org.junit.Test
import java.util.*

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 1866 👎 0

// ()   10

// (()) 1100
// ()() 1010

// ((())) 111000
// (())() 110010
// ()(()) 101100
// (()()) 110100
// ()()() 101010

// ()((())) 10111000
// ((()))() 11100010
// (((()))) 11110000
// ()(())() 10110010
// (())()() 11001010
// ((()))() 11100010
// (())()() 11001010
// ()()(()) 10101100
// (()()) 110100
// ()()() 101010

// ())( 1001
// )(() 0110
// )()( 0101
// ))(( 0011

// (())
// ()()
// ())(
// )(()
// )()(
// ))((

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionGenerateParenthesis {
    @Test
    fun generateParenthesis() {
        // generateParenthesis(2)
        var dp = Hashtable<String, List<String>>()
        println(generateParenthesisByDp(3, dp))
        // println(generateParenthesis(0))
    }

    // (a)b
    // a 和 b 为合法符号，可为空
    fun generateParenthesisByDp(n: Int, dp: Hashtable<String, List<String>>): List<String> {
        if (n == 0) {
            dp[n.toString()] = listOf()
            return listOf()
        }
        if (n == 1) {
            dp[n.toString()] = listOf("()")
            return listOf("()")
        }
        if (dp.containsKey(n.toString())) {
            return dp[n.toString()]!!
        }
        var result = ArrayList<String>()
        for (i in 0 until n) {
            if (generateParenthesisByDp(i, dp).isNullOrEmpty()) {
                // result.add("()" + )
                generateParenthesisByDp(n - 1 - i, dp).forEach { b ->
                    run {
                        result.add("()$b")
                    }
                }
                continue
            }
            if (generateParenthesisByDp(n - 1 - i, dp).isNullOrEmpty()) {
                // result.add("()" + )
                generateParenthesisByDp(i, dp).forEach { a ->
                    run {
                        result.add("($a)")
                    }
                }
                continue
            }
            generateParenthesisByDp(i, dp).forEach { a ->
                run {
                    generateParenthesisByDp(n - 1 - i, dp).forEach { b ->
                        run {
                            result.add("($a)$b")
                        }
                    }
                }
            }
        }
        dp[n.toString()] = result
        return result
        TODO()
    }
}
//leetcode submit region end(Prohibit modification and deletion)
